#define _CRT_SECURE_NO_WARNINGS 
#include<stack>

template<typename T>
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty())
        {
            while (!stack1.empty())
            {
                int tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        }
        int ret = stack2.top();
        stack2.pop();
        return ret;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};


/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
template<typename T>
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* p = head;
        int len = 0;
        if (head == NULL) {
            return {};
        }
        while (p) {
            p = p->next;
            len++;
        }
        vector<int> nums(len);
        p = head;
        for (int i = len - 1; i >= 0; i--) {
            nums[i] = p->val;
            p = p->next;
        }
        return nums;
    }
};
